package com.fyl.basic_algorithm.sorts;

/**
 * @author 冯永龙
 * @date 2021/3/22 15:05
 * 二分排序
 */

public class DitchSort {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int[] b = {1, 3, 3, 3, 3, 3, 3};
        System.out.println("普通方式实现二分：" + breach(a, a.length, 1));
        System.out.println("递归实现二分：" + breachInternally(a, 0, a.length - 1, 9));
        System.out.println("查找第一个值等于给定值的元素:" + bsearch(b, b.length, 3));
        System.out.println("查找最后一个值等于给定值的元素:" + bsearch_02(b, b.length, 3));
        System.out.println("查找第一个大于等于给定值的元素" + bsearch_03(b, b.length, 2));
        System.out.println("查找最后一个小于等于给定值的元素："+bsearch_04(b, b.length, 1));

    }

    //查找最后一个小于等于给定值的元素
    public static int bsearch_04(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid -1;
            } else {
                if ((mid == n - 1) || a[mid + 1] > value) {
                    return mid;
                }else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

    //查找第一个大于等于给定值的元素
    public static int bsearch_03(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] < value) {
                low = mid + 1;
            } else {
                if ((mid == 0) || a[mid - 1] < value) {
                    return mid;
                }
                high = mid - 1;
            }
        }

        return -1;
    }

    //查找最后一个值等于给定值的元素
    public static int bsearch_02(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                if ((mid == n - 1) || a[mid + 1] != value) {
                    return mid;
                }
                low = mid + 1;
            }
        }

        return -1;
    }

    //查找第一个值等于给定值的元素,1,3,3,3,3,3,3,
    public static int bsearch(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] < value) {
                low = mid + 1;
            } else if (a[mid] > value) {
                high = mid - 1;
            } else {
                if ((mid == 0) || a[mid - 1] != value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }

        return -1;
    }

    //普通方式实现二分查找，在不存在重复元素的有序数组中，查找值等于给定值的元素
    public static int breach(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] == value) {
                return mid;
            }
            if (a[mid] > value) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

    //递归实现二分查找，在不存在重复元素的有序数组中，查找值等于给定值的元素
    public static int breachInternally(int[] a, int low, int high, int value) {
        if (low > high) return -1;

        int mid = low + ((high - low) >> 1);
        if (a[mid] == value) {
            return mid;
        } else if (a[mid] < value) {
            return breachInternally(a, mid + 1, high, value);
        } else {
            return breachInternally(a, low, high - 1, value);
        }
    }
}
